#include "fibonacci_heap.h"
#include "constants.h"
#include "stdlib.h"
#include "string.h"
static void init_node_list(fibonacci_node *node)
{
	node->prev = node;
	node->aft = node;
	node->child = NULL;
	node->mark = 0;
	node->parent = NULL;
	node->degree = 0;
}
static fibonacci_node *remove_node_list(fibonacci_heap*heap,fibonacci_node *node)
{
	fibonacci_node *next = node->aft;
	next->prev = node->prev;
	node->prev->aft = next;
	if (heap->root == node)
	{
		heap->root = next;
	}
	return next;
}
static concat_heap_node_list(fibonacci_node *node_list1,fibonacci_node *node_list2)
{
	fibonacci_node *list1_prev,*list1_aft,*list2_prev,*list2_aft;
	list1_prev = node_list1;
	list1_aft = node_list1->aft;
	list2_prev = node_list2;
	list2_aft = node_list2->aft;

	list1_prev->aft = list2_aft;
	list1_aft->prev = list2_prev;
	list2_aft->prev = list1_prev;
	list2_prev->aft = list1_aft;
}
fibonacci_heap* fibonacci_heap_union(fibonacci_heap *heap1,fibonacci_heap *heap2)
{
	heap1->node_num += heap2->node_num;
	if (heap1->min_node->key > heap2->min_node->key)
	{
		heap1->min_node = heap2->min_node;
	}
	concat_heap_node_list(heap1->root,heap2->root);
	return heap1;
}
fibonacci_node *fib_heap_insert(fibonacci_heap *heap,int x)
{
	fibonacci_node *node = (fibonacci_node*)malloc(sizeof(fibonacci_node));
	init_node_list(node);
	node->key = x;
	if (NULL == heap->root)
	{
		heap->root = node;
		heap->node_num = 1;
		heap->min_node = node;
	}
	else
	{
		concat_heap_node_list(heap->root,node);
		heap->node_num++;
		if (heap->min_node->key > node->key)
		{
			heap->min_node = node;
		}
	}
	return node;
}
static insert_fib_node(fibonacci_node *father,fibonacci_node *son)
{
	father->degree ++;
	son->parent = father;
	son->prev = son;
	son->aft = son;
	son->mark = 0;
	if (NULL == father->child)
	{
		father->child = son;
	}
	else
	{
		concat_heap_node_list(father->child,son);
	}
}
void concolidate(fibonacci_heap *heap)
{
	int store_num = 1;
	fibonacci_node **temp_store;
	fibonacci_node *temp;
	while ((1<<store_num) <= heap->node_num)
	{
		store_num++;
	}
	store_num*=2;//for fi = (1+5^(1/2))/2
	temp_store = (fibonacci_node**)malloc(sizeof(fibonacci_node*)*store_num);
	memset(temp_store,0,sizeof(fibonacci_node*)*store_num);
	temp = heap->root;
	do 
	{
		int x = temp->degree;
		while (NULL != temp_store[x])
		{
			fibonacci_node* father,*son;
			if (temp_store[x]->key < temp->key)
			{
				father = temp_store[x];
				son = temp;
			}
			else
			{
				father = temp;
				son = temp_store[x];
			}
			temp_store[x] = NULL;
			remove_node_list(heap,son);
			insert_fib_node(father,son);
			temp = father;
			x++;
		}
		temp_store[x] = temp;
		temp = temp->aft;
	}while(temp != heap->root);
	free(temp_store);
}
fibonacci_node *fib_heap_extract_min(fibonacci_heap *heap)
{
	
	fibonacci_node *res = heap->min_node,*temp;
	if (NULL == heap->min_node)
	{
		return NULL;
	}
	heap->node_num--;
	if (0 == heap->node_num)
	{
		//empty
		heap->root = heap->min_node = NULL;
		return res;
	}
	if (heap->root->prev == heap->root)
	{
		//empty root but res->child not empty;
		heap->root = res->child;
	}
	else
	{
		remove_node_list(heap,res);
		temp = res->child;
		if (NULL != res->child)
		{
			do 
			{
				temp->parent = NULL;
			} while (temp != res->child);
			concat_heap_node_list(heap->root,res->child);
		}
	}
	concolidate(heap);
	heap->min_node = heap->root;
	temp = heap->root;
	do
	{
		if (temp->key < heap->min_node->key)
		{
			heap->min_node = temp;
		}
		temp = temp->aft;
	}while(temp != heap->root);
	return res;
}

fibonacci_heap* fib_heap_init()
{
	fibonacci_heap *res = (fibonacci_heap*)malloc(sizeof(fibonacci_heap));
	res->min_node = res->root = NULL;
	res->node_num = 0;
	return res;
}
void cut(fibonacci_heap *heap,fibonacci_node *father,fibonacci_node *son)
{
	father->degree--;
	if (father->child->aft == father->child)
	{
		father->child = NULL;
	}
	else
	{
		remove_node_list(heap,son);
	}
	son->aft = son;
	son->prev = son;
	son->parent = NULL;
	concat_heap_node_list(heap->root,son);
	son->mark = 0;
}

void cascade_cut(fibonacci_heap *heap,fibonacci_node* node)
{
	fibonacci_node *father;
	father = node->parent;
	if (NULL != father )
	{
		if(0 == node->mark)
		{
			node->mark = 1;
		}
		else
		{
			cut(heap,father,node);
			cascade_cut(heap,father);
		}
	}
}
void fib_heap_decrease_key(fibonacci_heap* heap,fibonacci_node *node,int k)
{
	fibonacci_node *father = node->parent;
	node->key = k;
	if (NULL != father && node->key < father->key)
	{
		cut(heap,father,node);
		cascade_cut(heap,father);
	}
	if (heap->min_node->key > node->key)
	{
		heap->min_node = node;
	}
}